public class Cat implements Stream {
    private StreamState stm1;
    private StreamState stm2;
    private StreamState activeStream;
    private HistoryStream historyStream = new HistoryStream();
    private boolean initialized = false;

    public Cat(Stream stream1, Stream stream2) {
        this.stm1 = new StreamState(stream1);
        this.stm2 = new StreamState(stream2);
        activeStream = this.stm1;
    }

    public String next() {
        String res = historyStream.next();
        if (res == null) {
            res = getFromStreams();
        }
        return res;
    }

    private String getFromStreams() {
        String res;
        if (!initialized) {
            res = doInit();
        } else {
            res = activeStream.getNext();
            if (res == null) {
                forceStreamSwitch();
                res = activeStream.getNext();
            }
            if (res != null) {
                res = catenate(res);
            }
            switchStreams();
        }
        historyStream.add(res);
        return res;
    }

    private String catenate(String newStr) {
        String res = null;
        if (activeStream == stm1) {
            String lastStrm2String = stm2.getLastString();
            if (lastStrm2String != null) {
                res = newStr + lastStrm2String;
            }
        } else {
            String lastStrm1String = stm1.getLastString();
            if (lastStrm1String != null) {
                res = lastStrm1String + newStr;
            }
        }
        return res;
    }

    private void forceStreamSwitch() {
        if (activeStream == stm1) {
            activeStream = stm2;
        } else {
            activeStream = stm1;
        }
    }

    private void switchStreams() {
        if (stm1.getIndex() == 0 || stm2.getIndex() == 0) {
            forceStreamSwitch();
            activeStream.setGoingBack(false);
        } else if (stm1.getIndex() == stm2.getIndex()) {
            forceStreamSwitch();
            activeStream.setGoingBack(true);
        }
    }

    private String doInit() {
        String res = null;
        String lastStrm1String = stm1.getLastString();
        String lastStrm2String = stm2.getLastString();
        if (lastStrm1String != null && lastStrm2String != null) {
            res = lastStrm1String + lastStrm2String;
        }
        initialized = true;
        return res;
    }

    public String prev() {
        return historyStream.prev();
    }

    public void reset() {
        stm1.reset();
        stm2.reset();
        historyStream.reset();
        activeStream = stm1;
    }

    private class StreamState {
        private Stream stream;
        private int index = 0;
        private boolean goingBack = false;
        private String lastString = null;

        private StreamState(Stream stream) {
            this.stream = stream;
            getNext(false);
        }

        public String getNext() {
            return getNext(true);
        }

        private String getNext(boolean changeIndex) {
            String res;
            if (goingBack) {
                res = stream.prev();
                if (changeIndex && res != null) {
                    index--;
                }
            } else {
                res = stream.next();
                if (changeIndex && res != null) {
                    index++;
                }
            }
            if (res != null) {
                lastString = res;
            }
            return res;
        }

        public String getLastString() {
            return lastString;
        }

        public int getIndex() {
            return index;
        }

        public void setGoingBack(boolean goingBack) {
            this.goingBack = goingBack;
        }

        public void reset() {
            stream.reset();
            index = 0;
            goingBack = false;
            lastString = null;
        }
    }
}
